package own.stu.jobgib.playown.alg.solution.dp;

import java.util.Arrays;

/**
 * 序列型动态规划
 */
public class SequenceType {

    public static void main(String[] args) {
        SequenceType s = new SequenceType();
        /*System.out.println(s.minCost(new int[][]{
                // {14, 2, 11}, {11, 14, 5}, {14, 3, 10}
                {1, 2, 3}, {1, 4, 6}
        }));*/

        /*System.out.println(s.minCostII(new int[][]{
         *//*{14, 2, 11},
                {11, 14, 5},
                {14, 3, 10},*//*
                {5},
                {10}

        }));*/
//        System.out.println(s.numWays(3, 2));

        /*System.out.println(s.maxProfit(2, new int[]{3, 2, 6, 5, 0, 3}));
        System.out.println(s.maxProfit(1, new int[]{2, 1}));*/

//        System.out.println(s.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println(s.lengthOfLIS(new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6}));
    }

    /**
     * <li>序列型动态规划:...前i个...最小/方式数/可行性<li/>
     * <li>在设计动态规划的过程中，发现需要知道油漆前N-1栋房子的最优策略中，房子N-2的颜色</li>
     * <li>如果只用fN-11,将无法区分</li>
     * <li>解决方法:记录下房子N-2的颜色一在房子N-2是红/蓝/绿色的情况下，油漆前N-1栋房子的最小花费</li>
     * <li>问题迎刀而解</li>
     * <li>序列+状态</li>
     */
    private void xx() {
    }

    /**
     * 515 · 房屋染色
     * 这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。
     * 费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用，依此类推。找到油漆所有房子的最低成本。
     * <p>
     * 所有费用都是正整数
     * <p>
     * 样例 1:
     * 输入: [[14,2,11],[11,14,5],[14,3,10]]
     * 输出: 10
     * 解释: 第一个屋子染蓝色，第二个染绿色，第三个染蓝色，最小花费：2 + 5 + 3 = 10.
     */
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        int n = costs.length;
        int[][] dp = new int[n][3];
        dp[0] = Arrays.copyOf(costs[0], 3);
        for (int i = 1; i < n; i++) {
            //dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);

            for (int j = 0; j < 3; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (j == k) continue;
                    dp[i][j] = Math.min(dp[i][j], costs[i][j] + dp[i - 1][k]);
                }
            }
        }
        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
    }

    /**
     * 516 · 房屋染色 II
     * 这里有n个房子在一列直线上，现在我们需要给房屋染色，共有k种颜色。每个房屋染不同的颜色费用也不同，你希望每两个相邻的房屋颜色不同
     * 费用通过一个nxk 的矩阵给出，比如cost[0][0]表示房屋0染颜色0的费用，cost[1][2]表示房屋1染颜色2的费用。找到油漆所有房子的最低成本。
     * 所有费用都是正整数
     * <p>
     * 样例1
     * 输入:
     * costs = [[14,2,11],[11,14,5],[14,3,10]]
     * 输出: 10
     * 说明: 三个屋子分别使用第1,2,1种颜色，总花费是10。
     */
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        int n = costs.length;
        int k = costs[0].length;
        if (n == 1) return costs[0][0]; // 题目要求相邻的颜色不同
        int[][] dp = new int[n + 1][k];
        int[] min = {-1, Integer.MAX_VALUE}, secMin = {-1, Integer.MAX_VALUE};
        // 初始化 第0个房子，染色的方式都是0
        // 从下标为1的房子开始计算
        for (int i = 1; i <= n; i++) {
            reset(min);
            reset(secMin);
            for (int j = 0; j < k; j++) {
                if (dp[i - 1][j] < min[1]) {

                    secMin[1] = min[1];
                    secMin[0] = min[0];

                    min[1] = dp[i - 1][j];
                    min[0] = j;
                } else if (dp[i - 1][j] < secMin[1]) {
                    secMin[1] = dp[i - 1][j];
                    secMin[0] = j;
                }
            }
            for (int j = 0; j < k; j++) {
                int preMin = j == min[0] ? secMin[1] : min[1];
                dp[i][j] = preMin + costs[i - 1][j];
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i : dp[n]) {
            ans = Math.min(ans, i);
        }
        return ans;
    }

    private void copy(int[] s, int[] t) {
        for (int i = 0; i < s.length; i++) {
            t[i] = s[i];
        }
    }

    private void reset(int[] s) {
        s[0] = -1;
        s[1] = Integer.MAX_VALUE;
    }

    /**
     * 514 · 栅栏染色
     * 我们有一个栅栏，它有n个柱子，现在要给柱子染色，有k种颜色可以染。
     * 必须保证不存在超过2个相邻的柱子颜色相同，求有多少种染色方案。
     * <p>
     * n和k都是非负整数
     * <p>
     * 例 1:
     * <p>
     * 输入: n=3, k=2
     * 输出: 6
     */
    public int numWays(int n, int k) {


        // TODO
        /*
        dp[i][0] 表示当前柱子i与前一个柱子颜色一样的染色方案      dp[i][0] = dp[i - 1][0]
        dp[i][1] 表示当前柱子i与前一个柱子颜色不一样的染色方案    dp[i][1] = k - 1
         *//*
        int[][] dp = new int[n][2];
        dp[0][0] = dp[0][1] = k;
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = dp[i - 1][1] * (k - 1);
        }
        return dp[n - 1][0] + dp[n - 1][1];*/

        /*
        dp[i] 表示柱子i的染色方案
        如果前一个柱子i-1与i-2相同，那么当前柱子i可用的颜色为k-1, dp[i] = dp[i - 1] * (k - 1)
         如果前一个柱子i-1与i-2不同，那么当前柱子i可用的颜色为k, dp[i] = dp[i - 1] * k
         */

        return -1;
    }

    /**
     * 序列+状态型dp
     * <li>当思考动态规划最后一步时，这一步的选择依赖于前一步的某种状态</li>
     * <li>初始化时，fO]代表前0个元素/前0天的情况</li>
     * - 与坐标型动态规划区别
     * <li>计算时，和代表前i个元素 (即元素0~i-1) 的某种性质</li>
     */
    private void yy() {
    }

    /**
     * 123. 买卖股票的最佳时机 III
     * 相关企业
     * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
     * <p>
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * <p>
     * 示例 1:
     * 输入：prices = [3,3,5,0,0,3,1,4]
     * 输出：6
     * 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     * 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        /**

         递推： 有点难想 ...
         dp[i][0]~dp[i][4] 分别表示第i天持有股票的状态 时的最大利润
         dp[i][0] 不操作 dp[i - 1][0] 由前一天延续
         dp[i][1] 第一次持有 dp[i - 1][1](延续) | dp[i - 1][0] - prices[i]（前一天不操作，第i天买入）
         dp[i][2] 第一次卖出 dp[i - 1][2](延续，前一天也是第一次卖出状态) + dp[i - 1][1] + price[i]
         dp[i][3] 第二次持有 dp[i - 1][3] | dp[i - 1][2] - price[i]
         dp[i][4] 第二次卖出 dp[i - 1][4] | dp[i - 1][3] + price[i]

         初始化：
         dp[0][0] = 0;// 这个状态可以不要
         dp[0][1] = 0 - prices[0];
         dp[0][2] = 0
         dp[0][3] = 0 - prices[0]
         dp[0][4] = 0;
         */
        int n = prices.length;
        int[][] dp = new int[n][4];
        dp[0][0] = dp[0][2] = -prices[0];
        dp[0][1] = dp[0][3] = 0;
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
        }
        return dp[n - 1][3];
    }

    /**
     * 188. 买卖股票的最佳时机 IV
     * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
     * <p>
     * 示例 1：
     * 输入：k = 2, prices = [2,4,1]
     * 输出：2
     * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2
     */
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        /*
        与III相比 由只能买卖至多2次变为了k次
         */
        int n = prices.length;
        int m = k * 2;
        int[][] dp = new int[n][m];
        for (int i = 0; i < m; i += 2) {
            dp[0][i] = -prices[0];
            dp[0][i + 1] = 0;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j += 2) {

                if (j == 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], -prices[i]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                }

                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }
        return dp[n - 1][m - 1];
    }

    /**
     * 300. 最长递增子序列
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
     * <p>
     * 示例 1：
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     */
    public int lengthOfLIS(int[] nums) {
        // 可以使用二分
        // 这里考虑的是dp
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        /*
        dp[i]表示以i为结尾的最长递增子序列
        那么对于（0~i-1)的子序列中
        存在 nums[j] < nums[i] 时 dp[j] + 1 = dp[i]
        如果nums[j] > nums[i] dp[i] = 1,表示只有自身，长度为1
         */
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] >= nums[i]) {
                    continue;
                }
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int ans = 0;
        for (int i : dp) {
            ans = Math.max(i, ans);
        }
        return ans;
    }
}
